//============================================================================
// Name        : demo.cpp
// Author      : Binda&Aeolus
// Version     :
// Copyright   : Copyright 2011 Binda&Aeolus; All Rights Reserved
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

//最长公共子序列
void LCSLength(int m, int n, char *x, char *y, int **c, int **b) {
	int i, j;
	for (i = 1; i <=m; i++)
		c[i][0] =0;
	for (i = 1; i <= n; i++)
		c[0][i] = 0;
	for (i = 1; i <= m; i++)
		for (j = 1; j <= n; j++) {
			if (x[i] == y[j]) {
				c[i][j] = c[i - 1][j - 1] + 1;
				b[i][j] = 1;

			} else if (c[i - 1][j] > c[i][j - 1]) {
				c[i][j] = c[i - 1][j];
				b[i][j] = 2;
			} else {
				c[i][j] = c[i][j - 1];
				b[i][j] = 3;
			}
			cout << "c[" << i << "][" << j << "]=" << c[i][j] << endl;
		}
}

void LCS(int i, int j, char *x, int **b) {
	if (i == 0 || j == 0)
		return;
	if (b[i][j] == 1) {
		LCS(i - 1, j - 1, x, b);
		cout << x[i];
	} else if (b[i][j] == 2)
		LCS(i - 1, j, x, b);
	else
		LCS(i, j - 1, x, b);
}

int main() {

	char x[11] = { ' ', 'b', 'a', 'c',
			       'd', 'e', 'e', 'e',
			       'e', 'r', 'e' };
	char y[10] = { ' ', 'b', 'c', 'd',
			       'e', 'a', 'e', 'e', 'r', 'e' };
	int m = 11;
	int n = 10;
	//申请空间
	int **b = new int*[m];
	for (int i = 0; i < m; i++)
		b[i] = new int[n];

	int **c = new int*[m];
	for (int i = 0; i < m; i++)
		c[i] = new int[n];

	//函数调用
	LCSLength(m - 1, n - 1, x, y, c, b);
	LCS(m - 1, n - 1, x, b);

	//释放空间
	for (int i = 0; i < m; i++) {
		delete[] c[n];
		delete[] b[n];
	}
	delete[] c;
	delete[] b;
	c = NULL;
	b = NULL;
	return 0;
}

//	for(int i=0;i<m;i++)
//		for(int j=0;j<n;j++)
//		{
//			c[i][j]=0;
//			b[i][j]=i*i;
//		}
//	for(int i=0;i<m;i++)
//			for(int j=0;j<n;j++)
//			{
//				cout<<c[i][j]<<endl;;
//				cout<<b[i][j]<<endl;
//			}
// Modified ON 5 MAY,2011
